public class test10 {
    class Solution {
        public int rob(int[] nums) {
            //有头就不能有尾
            //分别讨论
            if(nums==null || nums.length<1){
                return 0;
            }
            if(nums.length==1){
                return nums[0];
            }
            return Math.max(robMax(nums,0,nums.length-2),robMax(nums,1,nums.length-1));
        }

        private int robMax(int[] nums,int start,int end){
            //和基础的打家劫舍一样
            if(end-start+1 == 1){
                return nums[start];
            }
            int[] dp = new int[end-start+1];//注意dp数组定义时的长度，不可使用dp[start]，可能造成数组越界
            dp[0] = nums[start];
            dp[1] = Math.max(nums[start],nums[start+1]);//dp[1]对应从start到start+1的选择
            for(int i = 2;i<end-start+1;i++){
                dp[i] = Math.max(dp[i-1],dp[i-2]+nums[start+i]);
            }
            return dp[end-start];
        }
    }
}
